1060. Missing Element in Sorted Array
Medium

Given an integer array nums which is sorted in ascending order and all of its elements are unique and given also an integer k, return the kth missing number starting from the leftmost number of the array.

 

Example 1:

Input: nums = [4,7,9,10], k = 1
Output: 5
Explanation: The first missing number is 5.

Example 2:

Input: nums = [4,7,9,10], k = 3
Output: 8
Explanation: The missing numbers are [5,6,8,...], hence the third missing number is 8.

Example 3:

Input: nums = [1,2,4], k = 3
Output: 6
Explanation: The missing numbers are [3,5,6,7,...], hence the third missing number is 6.

 

Constraints:

  • 1 <= nums.length <= 5 * 104
  • 1 <= nums[i] <= 107
  • nums is sorted in ascending order, and all the elements are unique.
  • 1 <= k <= 108

 

Follow up: Can you find a logarithmic time complexity (i.e., O(log(n))) solution?
Accepted
66,103
Submissions
119,921
Seen this question in a real interview before?
Companies
Related Topics
Show Hint 1
First define a function f(x) that counts the number of missing elements until x.
Show Hint 2
Then use binary search with the given function f(x) to find the kth missing element.

Average Rating: 3.57 (49 votes)

Premium

Solution


Approach 1: One Pass

Intuition

The problem is similar to First Missing Positive and the naive idea would be to solve it in a similar way by one pass approach.

Let's first assume that one has a function missing(idx) that returns how many numbers are missing until the element at index idx.

fig

With the help of such a function the solution is straightforward :

  • Find an index such that missing(idx - 1) < k <= missing(idx). In other words, that means that kth missing number is in-between nums[idx - 1] and nums[idx].

    One even could compute a difference between kth missing number and nums[idx - 1]. First, there are missing(idx - 1) missing numbers until nums[idx - 1]. Second, all k - missing(idx - 1) missing numbers from nums[idx - 1] to kth missing are consecutive ones, because all of them are less than nums[idx] and hence there is nothing to separate them. Together that means that kth smallest is larger than nums[idx - 1] by k - missing(idx - 1).

  • Return kth smallest nums[idx - 1] + k - missing(idx - 1).

fic

The last thing to discuss is how to implement missing(idx) function.

Let's consider an array element at index idx. If there is no numbers missing, the element should be equal to nums[idx] = nums[0] + idx. If k numbers are missing, the element should be equal to nums[idx] = nums[0] + idx + k. Hence the number of missing elements is equal to nums[idx] - nums[0] - idx.

pic

Algorithm

  • Implement missing(idx) function that returns how many numbers are missing until array element with index idx. Function returns nums[idx] - nums[0] - idx.

  • Find an index such that missing(idx - 1) < k <= missing(idx) by a linear search.

  • Return kth smallest nums[idx - 1] + k - missing(idx - 1).

Implementation

Complexity Analysis

  • Time complexity: O(N)\mathcal{O}(N) since in the worst case it's one pass along the array.

  • Space complexity: O(1)\mathcal{O}(1) since it's a constant space solution.


Intuition

Approach 1 uses the linear search and doesn't profit from the fact that array is sorted. One could replace the linear search by a binary one and reduce the time complexity from O(N)\mathcal{O}(N) down to O(logN)\mathcal{O}(\log N).

The idea is to find the leftmost element such that the number of missing numbers until this element is less or equal to k.

fif

Algorithm

  • Implement missing(idx) function that returns how many numbers are missing until array element with index idx. Function returns nums[idx] - nums[0] - idx.

  • Find an index such that missing(idx - 1) < k <= missing(idx) by a binary search.

  • Return kth smallest nums[idx - 1] + k - missing(idx - 1).

Implementation

Complexity Analysis

  • Time complexity: O(logN)\mathcal{O}(\log N) since it's a binary search algorithm in the worst case when the missing number is less than the last element of the array.

  • Space complexity : O(1)\mathcal{O}(1) since it's a constant space solution.

Report Article Issue

Comments: 30
ltbtb_rise's avatar
Read More

approach one solution was made like a rocket science while a simple for loop could just do the job:

class Solution {
public:
    int missingElement(vector<int>& nums, int k) {
        int n=nums.size(),diff=0;
        for(int i=1;i<n;i++)
        {
            diff=nums[i]-nums[i-1]-1;
            if(diff>=k) return nums[i-1]+k;
            k-=diff;
        }
        return nums[n-1]+k;
    }
};

132
Show 3 replies
Reply
Share
Report
montabano1's avatar
Read More

I think using the phrase that approach 1 "doesn't profit from the fact that array is sorted." is wrong. If the array wasnt sorted we would not be able to find what numbers were missing?

43
Show 1 reply
Reply
Share
Report
bhushan55's avatar
Read More

the time complexity is not constant, you should only put for the worst case here.

35
Show 3 replies
Reply
Share
Report
sutirtho's avatar
Read More

This question should be marked hard.

42
Show 3 replies
Reply
Share
Report
ywen1995's avatar
Read More

The constant complexity is very misleading (or over simplified) here.

12
Reply
Share
Report
nlackx's avatar
Read More

The idea is to find the leftmost element such that the number of missing numbers until this element is smaller or equal to k.

should be greater

10
Reply
Share
Report
nyc_coder_84's avatar
Read More

Was asked this question in my Facebook onsite interview, 2nd question after I completed the first one in under 20 min, took a long time to arrive at the binary search solution with the help of the interviewer, but didn't have time in the end to code it all. If you haven't seen this question before, it is very difficult to see that binary search pattern especially in an interview setting.

6
Show 3 replies
Reply
Share
Report
steffi_keran's avatar
Read More

What is the intuition behind nums[idx - 1] + k - missing(idx - 1)?

5
Show 3 replies
Reply
Share
Report
ilkercankaya's avatar
Read More

Time Complexity is calculated by taking the worst-case into account. Saying that it is O(1) is extremely misleading for a lot of people. Please change it!

6
Reply
Share
Report
Jingles_-_-'s avatar
Read More

Hi, I have a doubt about approach 2.

Why is the else condition in binary search "right = pivot" rather than "right = pivot - 1"?

1
Reply
Share
Report

You don't have any submissions yet.

/23
Contribute
|||
Saved
Trie
This list is empty.